package DP.背包.每样1个;


import org.junit.Test;

import static MyUtils.MHUtils.debug_digui;

/**
 * 太太太重要
 * 为什么 L+=v[c] ,不 return时+v[c] ？
 * 答：
 * -> 只有 草稿 手跑,  试出来的
 * <p>
 * 应对面试
 * 二叉树
 * r c+L+R
 * 拿/不拿
 * L+=c
 * -> 若蒙了：草稿 手跑！！！！
 */
public class 背包_每样1个_后序 {
    int N = 3, W = 4;
    int[] w = new int[]{2, 1, 3};
    int[] v = new int[]{4, 2, 3};

    // 法1 L+=c.v -> 【用这个！！】
    int step = 0;
    public int maxVal(int cI, String cF, int faSumW) {
        debug_digui(step++, String.format("%s %s ",cI,cF)); //d1 参++
        if (cI == v.length) {
            debug_digui(--step, "return 0");//d2 --r0
            return 0;
        }

        int leftMaxVal = 0;
        if (faSumW + w[cI] <= W) {
            leftMaxVal = maxVal(cI + 1, "na", faSumW + w[cI]) + v[cI];
        }
        //825：这个没加[ci]就是不要cur -> 体现了dp[i]汉译的 “前” i个
        int rightMaxVal = maxVal(cI + 1, "buna", faSumW);

        debug_digui(--step, "return " + Math.max(leftMaxVal, rightMaxVal));//d3 --r果
        return Math.max(leftMaxVal, rightMaxVal);
    }

    // 法2 r c.+L+R
    public int maxVal2(int cI, String cFlag, int faSumW) {
        if (cI == v.length - 1) {
            return cFlag.equals("na") ? v[cI] : 0;
        }

        int leftMaxVal = 0;
        if (faSumW + w[cI + 1] <= W) {
            leftMaxVal = maxVal2(cI + 1, "na", faSumW + w[cI]);
        }
        int rightMaxVal = maxVal2(cI + 1, "buna", faSumW);

        return (cFlag.equals("na") ? v[cI] : 0) + Math.max(leftMaxVal, rightMaxVal);
    }


    @Test
    public void test() {
        int rotNa = maxVal(0, "na", 0); // 因为上面weight 只判断 fa+w[c+1] -> 汉：应该是 c=0时 fa有w[0]
        int rotBuna = maxVal(0, "buna", 0);
        System.out.println("RES:" + Math.max(rotNa, rotBuna));
    }
    @Test
    public void test2() {
        int rotNa = maxVal2(0, "na", w[0]); // 因为上面weight 只判断 fa+w[c+1] -> 汉：应该是 c=0时 fa有w[0]
        int rotBuna = maxVal2(0, "buna", 0);
        System.out.println("RES:" + Math.max(rotNa, rotBuna));
    }
}
